#pragma once
#include<iostream>
#include<vector>
#include <thread>
#include <mutex>
#include <algorithm>
#include<assert.h>
#include <unordered_map>

using std::cout;
using std::endl;

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif

const size_t MAXSIZE = 256 * 1024;
const size_t NUMFREESIZE = 208;
const size_t NPAGES = 129;
const size_t PAGE_SHIFT = 13;

#ifdef _WIN32
#include<Windows.h>

#else
//.. linux下头文件
#endif 


inline static void* SystemAlloc(size_t kpage) // kpage为页数,设定为8Kb一页
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

static void*& NextObj(void* obj)
{
	return *reinterpret_cast<void**>(obj);
}

class FreeList
{
public:
	void Push(void* obj)
	{
		// 头插
		NextObj(obj) = _freelist;
		_freelist = obj;
		++_size;
	}

	void PushList(void* start,void* end,size_t num)
	{
		NextObj(end) = _freelist;
		_freelist = start;
		void* cur = start;
		int i = 0;
		while (cur)
		{
			cur = NextObj(cur);
			++i;
		}
		if (num != i)
		{
			int x = 0;
		}
		_size += num;
	}

	void PopList(void*& start, void*& end, size_t maxsize)
 	{
		assert(maxsize <= _size);
		start = _freelist;
		end = start;
		for (size_t i = 0; i < maxsize - 1; ++i)
		{
			end = NextObj(end);
		}
		_size -= maxsize;
		_freelist = NextObj(end);
		NextObj(end) = nullptr;

	}

	void* Pop()
	{
		// 头删
		assert(_freelist);
		void* next = NextObj(_freelist);
		void* obj = _freelist;
		_freelist = next;
		--_size;
		return obj;
	}

	bool Empty()
	{
		return _freelist == nullptr;
	}

	size_t& MaxSize()
	{
    		return _maxsize;
	}

	size_t& Size()
	{
		return _size;
	}

private:
	void* _freelist = nullptr; // 管理归还内存的自由链表的头指针
	size_t _maxsize = 1;
	size_t _size = 0;
};

// 计算对象大小的对齐映射规则
// 整体控制在最多10%左右的内碎片浪费
// [1,128] 8byte对齐 freelist[0,16)
// [128+1,1024] 16byte对齐 freelist[16,72)
// [1024+1,8*1024] 128byte对齐 freelist[72,128)
// [8*1024+1,64*1024] 1024byte对齐 freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对齐 freelist[184,208)
struct SizeClass
{
	/*size_t _RoundUp(size_t size,size_t AlignNum)
	{
		size_t alignsize;
		if (size % AlignNum != 0)
		{
			alignsize = (size / AlignNum + 1) * AlignNum;
		}
		else
		{
			alignsize = size;
		}
		return alignsize;
	}*/

	static inline size_t _RoundUp(size_t size, size_t AlignNum)
	{
		return ((size + AlignNum - 1) & ~(AlignNum - 1));
	}
	// 计算对齐字节数
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8*1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64*1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256*1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	// 计算映射到哪个自由链表桶
	static inline size_t _Index(size_t size,size_t align_shift)
	{
		return ((size + (static_cast<size_t>(1) << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t size)
	{
		static size_t array[] = { 16,56,56,56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + array[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + array[0] + array[1];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8*1024, 10) + array[0] + array[1] + array[2];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64*1024, 13) + array[0] + array[1] + array[2] + array[3];
		}
		else
		{           
			assert(false);
			return -1;
		}
	}

	// 计算给多少个对象
	static inline size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		size_t num = MAXSIZE / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	// 计算一次向系统获取多少页(一页8K)
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT; // (num * size) / 8Kb
		if (npage == 0)
			npage = 1; // 至少给一页
		return npage;

	}

};

struct Span
{
	PAGE_ID _pageid = 0; // 大块内存起始页号
	PAGE_ID _n = 0; // 页的数量

	Span* _next = nullptr; // 双向循环结构
	Span* _prev = nullptr;

	size_t _ObjSize = 0; // 记录该span切分成小块内存的size

	size_t _useCount = 0; // 切好的小块内存给ThreadCache使用的计数
	bool _isUse = false; // 标志该span是否正在被使用
	void* _freelist = nullptr; // 切好的小块内存的自由链表
};

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	// 遍历spanlist
	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		// 在pos前插入
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void PushFront(Span* newspan)
	{
		Insert(Begin(), newspan);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

	}
private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};


//
//Span* GetOneSpan(SpanList& _freelist, size_t size);

